/*
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：1
示例 2：

输入：n = 5
输出：5
 

提示：

0 <= n <= 100
*/
#include<stdio.h>
#define Mod 1000000007
#define ll long long
//快速幂，该方式可以将算法时间复杂度压到 O(log n) 级别
//可以推导出重要结论
//((1,1);(1,0))^n * (F(1);F(0)) = (F(n+1);F(n))
//依次将斐波拉契数组转换成递推公式
void matrix_multi(ll A[2][2], ll B[2][2]){	//矩阵点乘运算
	long long C[2][2]={0};
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			C[i][j]=( (A[i][0] * B[0][j])%Mod + (A[i][1] * B[1][j])%Mod ) % Mod;
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			A[i][j]=C[i][j]%Mod;
}
int quick_pow(int A[2][2],int n){	//快速幂主函数
	ll base[2][2]={{A[0][0],A[0][1]},{A[1][0],A[1][1]}};
	ll res[2][2]={1,0,0,1};
	while(n){
		if(n&1)
			matrix_multi(res,base);	//表示res = res*base;
		matrix_multi(base,base);	//表示base*=base;
		n>>=1;
	}
	return res[0][0]%Mod;
	
}
int fib(int n){
	if(n<2)
		return n;
	int StartMatrix[2][2]={{1,1},{1,0}};
	return quick_pow(StartMatrix,n-1);
}


//记忆化搜索
//static int book[105]={0,1,1};	//保存递归时的数据
//int fib(int n){
//	if(book[n] || n==0)
//		return book[n];
//	return book[n]=(fib(n-1)%Mod + fib(n-2)%Mod)%Mod;
//}

//下方解法为单纯的递归求解，值得注意的是，递归中存在许多重复求解
//int fib(int n){
//	if(n==0||n==1)
//		return n;
//	long long n_1 = fib(n-1)%Mod + fib(n-2)%Mod;
//	return n_1%Mod;
//}

int main(){
	int n=0;
	scanf("%d",&n);
	printf("%d\n",fib(n));
	return 0;
}











